import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

import org.matheclipse.core.expression.F;
import org.matheclipse.core.expression.IntegerSym;
import org.matheclipse.core.interfaces.IAST;
import org.matheclipse.core.interfaces.IExpr;
import org.matheclipse.core.reflection.system.EulerPhi;

import apache.harmony.math.BigInteger;


public class RootSolver {
EulerPhi ephi;

public RootSolver(){
	ephi = new EulerPhi();
}
public int ePhi(int zsystem) throws ScriptException{
String stringResult= null;

ScriptEngineManager scriptManager = new ScriptEngineManager();
ScriptEngine engine_1 =scriptManager.getEngineByExtension("m");


    stringResult = (String) engine_1.eval("EulerPhi["+zsystem+"]");

	return Integer.parseInt(stringResult);
	
}
public String calcRSA(int n, int a, int d ) throws ScriptException{
	int[] val1= gcd(ePhi(n),a);
	System.out.println("gcd von " +ePhi(n) +" und " +a+ " ist = " +val1[0]);
	if(val1[0]!=1){
		throw new RuntimeException("gcc ist nicht 1");
		
	}
	int e = findInverse(ePhi(n),a); 
	System.out.println("e = " + e);
	BigInteger dBig = BigInteger.valueOf(d);
	BigInteger edBig = BigInteger.valueOf(e);
	BigInteger ndBig = BigInteger.valueOf(n);
	BigInteger adBig = BigInteger.valueOf(d);
	System.out.println("a = "+ adBig.toString());
	BigInteger bdBig = adBig.modPow(edBig, ndBig);
	System.out.println("B vor Modulo = "+ bdBig.toString());
	bdBig = bdBig.mod(ndBig);
	System.out.println("Restult = " +bdBig.toString());
	
	
	
	
	return bdBig.toString();
	
}

static int[] gcd(int p, int q) {
    if (q == 0)
       return new int[] { p, 1, 0 };

    int[] vals = gcd(q, p % q);
    int d = vals[0];
    int a = vals[2];
    int b = vals[1] - (p / q) * vals[2];
    return new int[] { d, a, b };
 }
public int ex(int a,int b, int n){
	int a1=a;
	int b1=b;
	for(int i = 0; i<b; i++){
		System.out.println(a1);
		a1=(a1*a1);
		a1=a1%n;
	}
	
	return a1;
}
public int findInverse(int d, int b){
	int result = b;
	int ntimes = 1;
	System.out.println("d = "+d+ " b = "+ b);
	//System.out.println("modshit =  " + (result*ntimes)%d);
	
	while(result*ntimes%d!=1){
		ntimes++;
		//System.out.println("ntimes = "+ntimes);
		//System.out.println("resultaslfdjl = "+result*ntimes%b);
		if (ntimes == 2000){break;}
	}
	
	return ntimes;
	
}
}
